2. Mathematical Foundations
2025-01-18
Directed vs Undirected Graphs 1
กราฟอาจจำแนกได้เป็น 2 ประเภทหลัก ได้แก่ กราฟแบบมีทิศทาง และแบบไม่มีทิศทาง ทั้งสองใช้แทนเครือข่ายที่มีลักษณะแตกต่างกัน
Directed vs Undirected Graphs 2
-
ถูกใช้แทนเครือข่ายที่ความสัมพันธ์มีลักษณะของทิศทางแบบเป็นเหตุเป็นผล เช่น
เป็นผู้ปกครองของ…
เป็นที่ปรึกษาของ…
ความสัมพันธ์แบบมีทิศทางสามารถมีลักษณะเป็นแบบย้อนกลับ (reciprocated ties ) ซึ่งเป็นไปได้ในเครือข่ายที่โหนดมีลักษณะของการปรึกษาหรือช่วยเหลือซึ่งกันและกัน
Directed vs Undirected Graphs 3
-
ใช้แทนเครือข่ายของความสัมพันธ์ที่ไม่มีทิศทาง เช่น
การพบเจอกัน
การแต่งงานกัน
การเป็นเพื่อนกัน รู้จักกัน
Multirelational/Multiplex Networks 1
เครือข่ายที่จุดยอดชุดเดียวกันมีความสัมพันธ์เกิดขึ้นได้หลายประเภท เรียกว่า multirelational หรือ multiplex networks
Isolates คือจุดยอดที่ไม่มีเส้นเชื่อม หรือ degree = 0
Pendants คือจุดยอดที่มี degree = 1
Multirelational/Multiplex Networks 2
ลองพิจารณา indegree ของ w1 และ w6 ในเครือข่ายทั้งสอง ความหมายที่ได้แตกต่างกันอย่างไร
Paths 1
วิถี (paths) หมายถึงลำดับของจุดยอดที่เชื่อมต่อกันด้วยเส้นเชื่อม (อาจเรียกว่าเป็นลำดับของ adjacent nodes) ที่ไม่มีการใช้เส้นเชื่อมหรือจุดยอดซ้ำ
- ลองพิจารณา w1 กับ w7 ด้านล่าง ความสัมพันธ์ของโหนดทั้งสองเป็นอย่างไร?
Paths 2
วิถี (paths) หมายถึงลำดับของจุดยอดที่เชื่อมต่อกันด้วยเส้นเชื่อม (อาจเรียกว่าเป็นลำดับของ adjacent nodes) ที่ไม่มีการใช้เส้นเชื่อมหรือจุดยอดซ้ำ
ลองพิจารณา w1 กับ w7 ด้านล่าง ความสัมพันธ์ของโหนดทั้งสองเป็นอย่างไร?
w1-s1-w3-w4-s1-w7 เป็น path หรือไม่?
Paths 3
วิถี (paths) หมายถึงลำดับของจุดยอดที่เชื่อมต่อกันด้วยเส้นเชื่อม (อาจเรียกว่าเป็นลำดับของ adjacent nodes) ที่ไม่มีการใช้เส้นเชื่อมหรือจุดยอดซ้ำ
ลองพิจารณา w1 กับ w7 ด้านล่าง ความสัมพันธ์ของโหนดทั้งสองเป็นอย่างไร?
w1-s1-w3-w4-s1-w7 เป็น path หรือไม่?
s4-w9-w8-w7 เป็น path หรือไม่?
Paths 4
คุณสมบัติของ Paths
- จุดเริ่มต้นและสิ้นสุด
Open Path: จุดเริ่มต้นและสิ้นสุดต่างกัน
Closed Path: จุดเริ่มต้นและสิ้นสุดเหมือนกัน
ไม่มีการใช้จุดยอดและเส้นเชื่อมซ้ำ ยกเว้นกรณี closed path
สำหรับเครือข่ายที่มีทิศทาง วิถีของการเดินจะต้องเป็นไปตามทิศทางของเส้นเชื่อมเท่านั้น
ความยาวของวิถี (path length) = จำนวนเส้นเชื่อมในวิถีนั้น
Paths 5
รอยเดิน (trails) หมายถึงลำดับของ adjacent nodes ที่ใช้จุดยอดซ้ำได้ โดยที่เส้นเชื่อมแต่จะเส้นจะถูกใช้ได้เพียงครั้งเดียว (ไม่มีการใช้เส้นเชื่อมซ้ำ)
- w1-s1-w3-w4-s1-w7 เป็น trail หรือไม่
Trials 1
รอยเดิน (trails) หมายถึงลำดับของ adjacent nodes ที่ใช้จุดยอดซ้ำได้ โดยที่เส้นเชื่อมแต่จะเส้นจะถูกใช้ได้เพียงครั้งเดียว (ไม่มีการใช้เส้นเชื่อมซ้ำ)
- w1-s1-w3-w4-s1-w7 เป็น trail หรือไม่
Trials 2
รอยเดิน (trails) หมายถึงลำดับของ adjacent nodes ที่ใช้จุดยอดซ้ำได้ โดยที่เส้นเชื่อมแต่จะเส้นจะถูกใช้ได้เพียงครั้งเดียว (ไม่มีการใช้เส้นเชื่อมซ้ำ)
w1-s1-w3-w4-s1-w7 เป็น trail หรือไม่
w8-w7-w9-w8-w7 เป็น trail หรือไม่
Trials 3
รอยเดิน (trails) หมายถึงลำดับของ adjacent nodes ที่ใช้จุดยอดซ้ำได้ โดยที่เส้นเชื่อมแต่จะเส้นจะถูกใช้ได้เพียงครั้งเดียว (ไม่มีการใช้เส้นเชื่อมซ้ำ)
w1-s1-w3-w4-s1-w7 เป็น trail หรือไม่
w8-w7-w9-w8-w7 เป็น trail หรือไม่
คุณสมบัติของ Trails
ใช้จุดยอดซ้ำได้
ไม่มีการใช้เส้นเชื่อมซ้ำ
มีทั้ง open และ closed trails
Walks
แนวเดิน (walks) หมายถึงลำดับของ adjacent nodes ที่ไม่มีการจำกัดเงื่อนไขเฉพาะ
คุณสมบัติของ Walks
ใช้จุดยอดและเส้นเชื่อมซ้ำได้
มีทั้ง open walks และ closed walks
- w8-w7-w9-w8-w7 เป็น walk หรือไม่
Paths, Trails, and Walks 2
แนวคิดของ paths, trails และ walks สามารถนำมาใช้แทนปรากฏการณ์เกี่ยวกับความสัมพันธ์ในเครือข่ายที่ต้องการอธิบายได้ เช่น
การแพร่กระจายข่าว (เชิงนินทา) : ลองพิจารณาลำดับของ adjacent nodes ต่อไปนี้
\[ W1 \rightarrow S1 \rightarrow W3 \rightarrow W4 \rightarrow S1 \rightarrow W7 \]
ลำดับข้างต้นเป็นลำดับประเภทไหน?
เป็นไปได้หรือไม่ที่การเดินทางของข่าวจะเดินทางในลำดับข้างต้น ?
Paths, Trails, and Walks 3
การแพร่ระบาดของเชื้อไวรัส ที่แพร่กระจายผ่านการมีปฏิสัมพันธ์
Walks
Trails
Paths
Paths, Trails, and Walks 4
การโต้ตอบกระทู้ใน discussion board
Walks
Trails
Paths
Geodesics
Geodesic distance: หรือ distance หมายถึง ระยะทางสั้นที่สุดของแนวเดิน (walk) ที่วัดจากจำนวนเส้นเชื่อมที่ใช้เชื่อมต่อจุดเริ่มต้นและจุดสิ้นสุดของแนวเดินนั้น
พิจารณา path ต่อไปนี้
w3-w4-s1
w3-w1-s1
Note: จะเห็นว่า geodesic distance ใช้บ่งชี้หรือสะท้อนการเดินทางของสิ่ง ๆ ใดในเครือข่ายว่าภายใต้สถานการณ์ที่ดีที่สุด การเดินทางของสิ่ง ๆ นั้นอาจจะต้องใช้เวลา
Components 1
ส่วนประกอบ (components) หมายถึงกลุ่มของโหนดที่ใหญ่ที่สุด (maximal set) ที่สามารถเชื่อมถึงกันได้ด้วย path อย่างน้อยหนึ่ง path
มี path จาก Holly ไปยัง Brazey หรือไม่?
\(\{Bill, Don, Michael\}\) ถือเป็น Component หรือไม่ เพราะ?
\(\{Gery, Russ\}\) เป็น component หรือไม่?
\(\{Carol \}\) เป็น component หรือไม่
Component ที่ใหญ่ที่สุดมีใครบ้าง?
Components 2
ส่วนประกอบ (components) หมายถึงกลุ่มของโหนดที่ใหญ่ที่สุด (maximal set) ที่สามารถเชื่อมถึงกันได้ด้วย path อย่างน้อยหนึ่ง path
Component อาจจำแนกเป็น 2 ประเภท
Weak Connected Component: กลุ่มของโหนดที่ใหญ่ที่สุดที่สามารถเชื่อมถึงกันได้ผ่าน path โดยไม่สนใจทิศทางของเส้นเชื่อม
Strong Connected Component: กลุ่มของโหนดที่เชื่อมกันด้วย path ที่สนใจทิศทาง
Bridges & Cutpoints 1
Bridge หมายถึง เส้นเชื่อม \(e\) ในกราฟ \(G\) ที่เมื่อลบเส้นเชื่อมดังกล่าวจากกราฟจะเพิ่มจำนวน components ในกราฟ
Cutpoints หมายถึง โหนดในกราฟที่เมื่อถูกลบออกไปพร้อมกับเส้นเชื่อมทั้งหมดที่เกี่ยวข้อง จะทำให้เพิ่มจำนวน component ในกราฟ
Bridges & Cutpoints 2
ระบุเส้นเชื่อมที่เป็น Bridges
ระบุโหนดที่เป็น Cutpoints
Cohesion 2: Adjacency
Matrix products 1
กำหนดให้ \(A\) และ \(B\) เป็นเมทริกซ์ที่สามารถคูณกันได้ ผลคูณระหว่างทั้งสองเมทริกซ์ \(C = AB\) สามารถคำนวณได้ตามนิยามดังนี้
\[ c_{ij} = \sum_{k} a_{ik}b_{kj} \]
ผลลัพธ์ที่ได้คือผลรวมเชิงเส้นระหว่างสมาชิกในแถวของ A กับสมาชิกในคอลัมน์ของ B
https://charchithowitzer.medium.com/matrix-multiplication-why-is-it-a-big-deal-cc8ef7490008
Matrix products 4
Matrix products 7
ตัวอย่างด้านล่างแสดงผลคูณ \(FF\) แปลว่า
มองได้มั้ยว่าเป็นจำนวนการเดิน (walks) ที่มีความยาวเท่ากับ 2 หน่วย จากโหนด \(i\) ไปยัง \(j\)
I1 I3 W1 W2 W3 W4 W5 W6 W7 W8 W9 S1 S2 S4
I1 1 0 1 0 0 1 0 0 0 0 0 1 0 0
I3 0 0 0 0 0 0 0 0 0 0 0 0 0 0
W1 1 0 3 0 2 2 0 0 1 0 0 2 0 0
W2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
W3 0 0 2 0 4 2 0 0 1 0 0 2 0 0
W4 1 0 2 0 2 3 0 0 1 0 0 2 0 0
W5 0 0 0 0 0 0 0 0 0 0 0 0 0 0
W6 0 0 0 0 0 0 0 0 0 0 0 0 0 0
W7 0 0 1 0 1 1 0 0 3 1 1 0 0 2
W8 0 0 0 0 0 0 0 0 1 3 2 1 0 1
W9 0 0 0 0 0 0 0 0 1 2 3 1 0 1
S1 1 0 2 0 2 2 0 0 0 1 1 4 0 0
S2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
S4 0 0 0 0 0 0 0 0 2 1 1 0 0 2
Matrix products 8
- ตัวอย่างด้านล่างแสดงผลคูณ \(F^3\) แปลว่า
I1 I3 W1 W2 W3 W4 W5 W6 W7 W8 W9 S1 S2 S4
I1 0 0 2 0 4 2 0 0 1 0 0 2 0 0
I3 0 0 0 0 0 0 0 0 0 0 0 0 0 0
W1 2 0 6 0 8 7 0 0 2 1 1 8 0 0
W2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
W3 4 0 8 0 6 8 0 0 2 1 1 9 0 0
W4 2 0 7 0 8 6 0 0 2 1 1 8 0 0
W5 0 0 0 0 0 0 0 0 0 0 0 0 0 0
W6 0 0 0 0 0 0 0 0 0 0 0 0 0 0
W7 1 0 2 0 2 2 0 0 2 6 6 6 0 2
W8 0 0 1 0 1 1 0 0 6 4 5 1 0 5
W9 0 0 1 0 1 1 0 0 6 5 4 1 0 5
S1 2 0 8 0 9 8 0 0 6 1 1 6 0 2
S2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
S4 0 0 0 0 0 0 0 0 2 5 5 2 0 2
Matrix products 10
\(A \times A^T\) หมายถึงจำนวนโหนดที่มีความสัมพันธ์หรือเชื่อมโยงกับทั้ง \(j\) และ \(j\)
\(F \times F^T\) หมายถึงจำนวนเพื่อนร่วมกันระหว่าง \(i\) กับ \(j\)
\(C \times C^T\) หมายถึงจำนวนคู่ขัดแย้งร่วมกันระหว่าง \(i\) กับ \(j\)
ตัวอย่างด้านล่างแสดงผลลัพธ์จาก \(F \times F^T\)
I1 I3 W1 W2 W3 W4 W5 W6 W7 W8 W9 S1 S2 S4
I1 1 0 1 0 0 1 0 0 0 0 0 1 0 0
I3 0 0 0 0 0 0 0 0 0 0 0 0 0 0
W1 1 0 3 0 2 2 0 0 1 0 0 2 0 0
W2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
W3 0 0 2 0 4 2 0 0 1 0 0 2 0 0
W4 1 0 2 0 2 3 0 0 1 0 0 2 0 0
W5 0 0 0 0 0 0 0 0 0 0 0 0 0 0
W6 0 0 0 0 0 0 0 0 0 0 0 0 0 0
W7 0 0 1 0 1 1 0 0 3 1 1 0 0 2
W8 0 0 0 0 0 0 0 0 1 3 2 1 0 1
W9 0 0 0 0 0 0 0 0 1 2 3 1 0 1
S1 1 0 2 0 2 2 0 0 0 1 1 4 0 0
S2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
S4 0 0 0 0 0 0 0 0 2 1 1 0 0 2
Social Relations and Implications
ความสัมพันธ์ทางสังคมแต่ละประเภทจะมีโครงสร้าง ความหมาย และผลกระทบที่แตกต่างกันต่อจุดยอดที่เกี่ยวข้อง เช่น
ความสัมพันธ์ในเครือข่ายมิตรภาพ จุดยอดที่มี degree จำนวนมากจะหมายถึงความนิยม
ความสัมพันธ์ในเครือข่ายการนินทา
ความสัมพันธ์ในเครือข่ายความเกลียดชังกัน
ผู้วิเคราะห์มักออกแบบ ให้ทุกเส้นเชื่อมในกราฟเป็นความสัมพันธ์แบบเดียวกัน เช่น
\(G(V,E)\) เป็นกราฟความสัมพันธ์แบบเพื่อนสนิทในชั้นเรียน
\(H(V,A)\) เป็นกราฟความสัมพันธ์ให้คำปรึกษาระหว่างเพื่อน